package greedy;

/**
 * 贪心算法：
 * 已知一些孩子和一些糖果，每个孩子有需求因子g，每个糖果有大小s，当 某个糖果的大小s >= 某个孩子的需求因子g时，
 * 代表该糖果可以满足该孩子；求使用这 些糖果，最多能满足多少孩子？(注意，某个孩子最多只能用1个糖果满足)
 * 例如，需求因子数组g = [5, 10, 2, 9, 15, 9]；糖果大小数组s = [6, 1, 20, 3, 8]；最多可以满足3个孩子。
 * @author le
 */
public class GiveCandies
{
    public static void main(String[] args)
    {
        int[] g = {5, 10, 2, 9, 15, 9};
        int[] s = {1, 3, 6, 8, 20};
        sort(g, 0, g.length-1);
        sort(s, 0, s.length-1);
        int i = 0;
        int j = 0;

        while(i < g.length && j < s.length){
            if (s[j] > g[i]){
                i++;
            }
            j++;
        }
        System.out.println(i);
    }

    public static void sort(int[] arr, int left, int right){
        if (left < right){
            int key = arr[left];

            int i = left;
            int j = right;

            while(i < j){

                while(i < j && arr[j] > key){
                    j--;
                }
                if (i < j){
                    arr[i++] = arr[j];
                }
                while(i < j && arr[i] < key){
                    i++;
                }
                if (i < j){
                    arr[j--] = arr[i];
                }
            }
            arr[i] = key;
            sort(arr, left, i-1);
            sort(arr,i+1,right);

        }
    }
}
